package linkedlist.leetcode_725;

public class SplitListToParts {
    public ListNode[] splitListToParts(ListNode root, int k) {
        //计算链表长度
        int length = 0;
        ListNode cur = root;
        while(cur != null){
            cur = cur.next;
            length++;
        }

        cur = root;

        //分成k部分，每一个部分有 length / k 个节点
        int size = length / k;
        //前 length % k 部分 额外多一个节点
        int extra = length % k;

        //初始化数组大小
        ListNode[] res = new ListNode[k];

        //外层控制每一个部分，内层来对每一个部分进行处理
        //共有k个部分
        for (int i = 0; i < k; i++){
            ListNode head = cur;
            for(int j = 1; j < size + (i < extra ? 1 : 0); j++){
                if(cur != null) cur = cur.next;
            }
            //断链
            if(cur !=null){
                ListNode next = cur.next;
                cur.next = null;
                cur = next;
            }
            res[i] = head;
        }
        return res;
    }
}
